// Time:  O(n)
// Space: O(1)

#include <string>
#include <vector>

using namespace std;


// Time:  O(n)
// Space: O(h)
class Solution {
public:
    int scoreOfParentheses(string s) {
        vector<int> stack{0};
        for (const auto& c : s) {
            if (c == '(') {
                stack.push_back(0);
            } else {
                const auto last = stack.back(); 
                stack.pop_back();
                stack.back() += max(1, 2 * last);
            }
        }
        return stack.front();
    }
};
